#include "global.h"
#include "cvt.h"
#include "kdtree.h"

Hierarchy::Hierarchy (Polygon & boundary)
{
  this->bound = boundary;
  this->cvt.set_bound(boundary);
  root = NULL;
}
Hierarchy::~Hierarchy()
{
   destroy_tree(root);
}
void Hierarchy::split_bound(Polygon & bound, Polygon & b1, Polygon & b2, int layer)
{
  //Now we only consider the problem in rectangle.
  //We can generalize the problem later;
  assert (bound.size() == 4);
  assert (true == bound.is_simple());
  Point p1 = bound[0];
  Point p2 = bound[2];
  Point tl (std::min (p1.x(),p2.x()), std::min (p1.y(), p2.y()));
  Point br(std::max (p1.x(),p2.x()), std::max (p1.y(), p2.y()));
  //If layer is an odd, we split x direction otherwise we split y direction
  b1.clear();
  b2.clear();
  if (layer % 2)
    {
      b1.push_back (Point (tl.x(), br.y()));
      b1.push_back (Point (tl.x(), tl.y()));
      b1.push_back (Point ((tl.x() + br.x())/2, tl.y()));
      b1.push_back (Point ((tl.x() + br.x())/2, br.y()));

      b2.push_back (Point ((tl.x() + br.x())/2, br.y()));
      b2.push_back (Point ((tl.x() + br.x())/2, tl.y()));
      b2.push_back (Point (br.x(), tl.y()));
      b2.push_back (Point (br.x(), br.y()));
    }
  else
    {
      b1.push_back (Point (tl.x(), br.y()));
      b1.push_back (Point (tl.x(), (tl.y() + br.y())/2));
      b1.push_back (Point (br.x(), (tl.y() + br.y())/2));
      b1.push_back (Point (br.x(), br.y()));

      b2.push_back (Point (br.x(), (tl.y() + br.y())/2));
      b2.push_back (Point (tl.x(), (tl.y() + br.y())/2));
      b2.push_back (Point (tl.x(), tl.y()));
      b2.push_back (Point (br.x(), tl.y()));
    }

}

void Hierarchy::refine (std::vector<Point> & sites, TreeNode * node)
{

  assert (node != NULL);
  std::vector<int> v_index;
  //std::vector<Point> v_p;

  //Extract all the node's index;
  std::deque<TreeNode * > queue;
  TreeNode * top;
  queue.push_back (node);
  while (queue.size())
    {
      top = queue.front();
      queue.pop_front();
      if (top->count == 1)
	{
	  v_index.push_back(top->index);
	}
      if (top->left != NULL) queue.push_back(top->left);
      if (top->right != NULL) queue.push_back(top->right);
    }

  for (unsigned i = 0; i < v_index.size(); ++i)
  {
	Polygon face;
	Point cen;
	cvt.convert_face_region(i, face);
	centroid(face, cen);
	cvt.move(i, cen);  
	sites[v_index[i]] = cen;
  }
}

void Hierarchy::insert (std::vector<Point> & sites, unsigned index)
{
  unsigned cvt_index = this->cvt.insert(sites[index]);
  assert (cvt_index == index);
  if (NULL == root)
    {
      root = new TreeNode; 
      root->bound = this->bound;
      root->index = index;
      root->layer = 0;
      root->count = 1;
    }
  else
    {
      Point p = sites[index];
      TreeNode * its = root;
      TreeNode * upits = root; 
      Polygon b1,b2;
      while (NULL != its)
	{
	  split_bound (its->bound, b1, b2, its->layer);
	  upits = its;
	  if ((NULL != its->left) && is_in (b1, b2, p, 0))
	    {
	      //In the left children
	      its->count += 1;
	      its = its->left;
	    }
	  else if ((NULL != its->right) && is_in (b2, b1,p, 1 ))
	    {
	      //In the right right
	      its->count += 1;
	      its = its->right;
	    }
	  else
	    {
	      //At least one of the its's children is null;
	      //we need to add it a children;

	      its->count++;
	      split_bound (its->bound, b1, b2, its->layer);
	      
	      if (its->right !=NULL && is_in (b1, b2, p, 0) && its-> left == NULL)
	      {
		its->left = new TreeNode;
		its->left->bound = b1;
		its->left->layer = its-> layer + 1;
		its->left->count = 1;
		its->left->index = index;
		return ;	      	
	      }
	      else if (its->left !=NULL && is_in (b2, b1, p, 1) && its-> right == NULL)
	      {
		its->right = new TreeNode;
		its->right->bound = b2;
		its->right->layer = its-> layer + 1;
		its->right->count = 1;
		its->right->index = index;
		return ;	      		      
	      }
	      else
	      
	      if (its->left == NULL && its->right == NULL)
	      {
		  Point p2 = sites[its->index];
		  int index2 = its->index;
		  its->index = -1;
		  int ac_layer = its->layer;
		  while ( (is_in (b1, b2, p, 0) && is_in (b1, b2, p2, 0) )
			  || (is_in (b2, b1, p, 1) && is_in (b2, b1, p2, 1) ))
		    {
		      //std::cout<<"hello"<<std::endl;
		      ac_layer++;
		      if (is_in (b1, b2, p, 0))
			{
			  its->left = new TreeNode;
			  its->left->bound = b1;
			  its->left->layer = its-> layer + 1;
			  its->left->count = 2;
			  its->left->index = -1;
			  its = its->left;
			  split_bound (its->bound, b1, b2, ac_layer);

			}
		      else 
			{
			  its->right = new TreeNode;
			  its->right->bound = b2;
			  its->right->layer = its-> layer + 1;
			  its->right->count = 2;
			  its->right->index = -1;
			  its = its->right;
			  split_bound (its->bound, b1, b2, ac_layer);
			}
		    }
		  if (is_in (b1, b2, p, 0))
		    {
		      its->left = new TreeNode;
		      its->left-> bound = b1;
		      its->left->index = index;
		      its->left->layer = ac_layer + 1;
		      its->left-> count = 1;
		      
		    }
		  else
		    {
		      its->right = new TreeNode;
		      its->right-> bound = b2;
		      its->right->index = index;
		      its->right->layer = ac_layer + 1;
		      its->right-> count = 1;
		      
		    }
		  if (is_in (b1, b2, p2, 0))
		    {
		      its->left = new TreeNode;
		      its->left-> bound = b1;
		      its->left->index = index2;
		      its->left->layer = ac_layer + 1;
		      its->left-> count = 1;
		      
		    }
		  else
		    {
		      its->right = new TreeNode;
		      its->right-> bound = b2;
		      its->right->index = index2;
		      its->right->layer = ac_layer + 1;
		      its->right-> count = 1;
		    }
		  return;
		}
	    }
	}
    }
}


void Hierarchy::hierarchy_tessellation (std::vector<Point> & sites )
{
  recursive_refine (sites, root);
  //refine (sites, root);
}

void Hierarchy::recursive_refine (std::vector<Point> & sites, TreeNode * node )
{
  if (node->count <= 2) 
    {
      /*
      for (int i = 0; i < 4; ++i)
	{
	  refine (sites, node);
	}
      */
      return ;
    }
  else
    {
      if (node->left != NULL) recursive_refine (sites, node->left);
      if (node->right != NULL) recursive_refine (sites, node->right);
      
      for (int i = 0; i < 1; ++i)
	{
	  refine (sites, node);
	}
      
      //refine (sites,node);
    }
}
void Hierarchy::output_result (std::vector<Point> & v_p)
{
  traverse (root, v_p);
}

void Hierarchy::destroy_tree (TreeNode* node)
{
  if (NULL != node)
    {
      destroy_tree (node->left);
      destroy_tree (node->right);
      delete node; 
    }
}

void LookasideHierarchy::hierarchy_tessellation (std::vector<Point> & sites )
{
  recursive_refine(sites, root, NULL, root->bound);
}
void LookasideHierarchy::recursive_refine (std::vector<Point> & sites, TreeNode * node, TreeNode * aside, Polygon & bound)
{
  if (node->count <= 1) 
    {
    	//refine (sites, node);
    	return ;
    }
  else
    {
      if (node->left != NULL) 
      	recursive_refine (sites, node->left, node->right, node->bound);
      if (node->right != NULL) 
      	recursive_refine (sites, node->right, node->left, node->bound);
      
      for (int i = 0; i < 1; ++i)
	{
	  refine (sites, node, aside, bound);
	}
      
      //refine (sites,node);
    }
}
void LookasideHierarchy::refine (std::vector<Point> & sites, TreeNode * node)
{
/*
  assert (node != NULL);
  std::vector<int> v_index;
  std::vector<Point> v_p;

  //Extract all the node's index;
  std::deque<TreeNode * > queue;
  TreeNode * top;
  queue.push_back (node);
  while (queue.size())
    {
      top = queue.front();
      queue.pop_front();
      if (top->count == 1)
	{
	  v_index.push_back(top->index);
	}
      if (top->left != NULL) queue.push_back(top->left);
      if (top->right != NULL) queue.push_back(top->right);
    }

  for (unsigned i = 0; i < v_index.size(); ++i)
    {
      v_p.push_back(sites[v_index[i]]);
    }

  std::vector<Polygon> faces;
  Bounded_voronoi bv(node->bound, v_p);
  bv.tessellation (faces);
  v_p.clear();
  faces_centroid(faces, v_p);

  for (unsigned i = 0; i < v_p.size(); ++i)
    {
      sites[v_index[i]] = v_p[i];
    }

  static int counter = 0;
  if (node == root)
    {
      counter ++;
      if (counter == 10)
	{
	  std::cout<<faces.size()<<std::endl;
	  for (unsigned i = 0; i < v_index.size(); ++i)
	    {
	      std::cout<<faces[i]<< std::endl;
	    }
	  std::cout<<endl;
	}
    }
*/
}
void LookasideHierarchy::refine (std::vector<Point> & sites, TreeNode * node, TreeNode * aside, Polygon & bound)
{
/*
  assert (node != NULL);
  std::vector<int> v_index_node, v_index_aside;
  std::vector<Point> v_p;

  //Extract all the node's index;
  std::deque<TreeNode * > queue;
  TreeNode * top;
  queue.push_back (node);
  while (queue.size())
    {
      top = queue.front();
      queue.pop_front();
      if (top->count == 1)
	{
	  v_index_node.push_back(top->index);
	}
      if (top->left != NULL) queue.push_back(top->left);
      if (top->right != NULL) queue.push_back(top->right);
    }

  for (unsigned i = 0; i < v_index_node.size(); ++i)
    {
      v_p.push_back(sites[v_index_node[i]]);
    }
  
  //Extract all the aside's index
  if (aside !=NULL)
  {
  	queue.clear();
  	queue.push_back (aside);
	while (queue.size())
    	{
      		top = queue.front();
      		queue.pop_front();
      		if (top->count == 1)
		{
	  		v_index_aside.push_back(top->index);
		}
      		if (top->left != NULL) queue.push_back(top->left);
      		if (top->right != NULL) queue.push_back(top->right);
    	} 	
  	for (unsigned i = 0; i < v_index_aside.size(); ++i)
    	{
      		v_p.push_back(sites[v_index_aside[i]]);
    	}    	
  }
  unsigned st_node = v_index_node.size();
  //unsigned st_aside = v_index_aside.size();
  
  
  //Refine v_index_node index nodes with regards to v_index_aside
  
  
  
  std::vector<Polygon> faces;
  Bounded_voronoi bv(bound, v_p);
  bv.tessellation (faces);
  v_p.clear();
  faces_centroid(faces, v_p);

  for (unsigned i = 0; i < st_node; ++i)
    {
      sites[v_index_node[i]] = v_p[i];
    }
*/
}
